package Exams.UCloud;

public class q2 {
    public int firstMissingPositive(int[] nums) {

        /**
         * leetcode 41题原题 缺失的第一个正数
         * 如果数组中包含 x in [1, N]，那么恢复后，数组的第 x - 1 个元素为 x。
         * 具体恢复手段可以看官方题解说明：可以对数组进行一次遍历，对于遍历到的数 x=nums[i]，如果 x∈[1,N]，我们就知道 x 应当出现在数组中的 x−1 的位置，
         * 因此交换 nums[i] 和 nums[x−1]，这样 x 就出现在了正确的位置
         * 最后只要找出位置不对应的，就得到了答案
         */
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;

    }
}
